package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/01/29 08:41
 **/

/**
 * 题目 ：爬楼梯
 * 题目详述 ：
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 提示：
 * 1 <= n <= 45
 */
public class ClimbStairs {
    /**
     * 思路 ：
     * 假设f(i)为到达第i解楼梯所有可能方法的数量;
     *
     * 状态转移方程 ：
     * 特殊情况 ：
     * （1）当i == 1时，即只存在向上移动一步的情况 ：f(1) = 1;
     * （2）当i == 2时，即只存在向上移动两次一步/向上移动一次两步的情况 ：f(2) = 2;
     * 一般情况 ：
     * (1)当最后爬到第i阶台阶的步数是1步的话，即f(i) = f(i-1);
     * (2)当最后爬到第i阶台阶的步数是2步的话，即f(i) = f(i-2);
     * ===> f(n) = f(i-1) + f(i-2);
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        // 需要注意的是，n的取值范围为[1,45];
//        int[] dp = new int[n];
//        dp[0] = 1;
//        if(n > 1){
//            dp[1] = 2;
//            for(int i = 2; i < n; i++){
//                dp[i] = dp[i - 1] + dp[i - 2];
//            }
//        }
//        return dp[n - 1];

        /*
         为啥将dp辅助数组大小定为2呢？
         即，由于要求解f(i)，所依赖的是f(i-1) && f(i-2);
         ===> 即，只需要存储f(i-1)和f(i-2)结果即可;
         */
        int[] dp = new int[2];
        dp[0] = 1;
        if(n > 1){
            dp[1] = 2;
            for(int i = 2; i < n; i++){
                dp[i % 2] = dp[(i - 1) % 2] + dp[(i - 2) % 2];
            }
        }
        return dp[(n - 1) % 2];
    }
}
